package sjjg.sort;

public class shell_sort {
    public static void main(String[] args) {
        int arr[]={1,6,3,8,9,11,2,5,7,12,9,9,9,9,9};
        int[] shellSort = shellSort(arr);
        for (int i : shellSort) {
            System.out.print(i+" ");
        }
    }

    public static int[] shellSort(int[]arr){
        //确定h的值
        int h=1;
        while (h<=arr.length/2){
            h=2*h+1;
        }
        //循环进行多趟排序
        int temp;//用于变量交换
        while (h>=1){
            for(int i=h;i<arr.length;i++){
                for(int j=i;j>=h;j-=h){
                    if(arr[j]<arr[j-h]){
                        temp=arr[j-h];
                        arr[j-h]=arr[j];
                        arr[j]=temp;
                    }else {
                        break;
                    }
                }
            }
            h/=2;//一趟结束后让h除于2
        }
        return arr;
    }
}
